Minimization of Akaike's Information Criterion in Linear Regression Analysis via Mixed Integer Nonlinear Program

摘要

Akaike's information criterion (AIC) is a measure of the quality of astatistical model for a given set of data. We can determine the beststatistical model for a particular data set by the minimization of the AIC.Since we need to evaluate exponentially many candidates of the model by theminimization of the AIC, the minimization is unreasonable. Instead, stepwisemethods, which are local search algorithms, are commonly used to find a betterstatistical model though it may not be the best. We propose a branch and bound search algorithm for a mixed integer nonlinearprogramming formulation of the AIC minimization by Miyashiro and Takano (2015).More concretely, we propose methods to find lower and upper bounds, andbranching rules for this minimization. We then combine them with SCIP, which isa mathematical optimization software and a branch-and-bound framework. We showthat the proposed method can provide the best statistical model based on AICfor small-sized or medium-sized benchmark data sets in UCI Machine LearningRepository. Furthermore, we show that this method finds good quality solutionsfor large-sized benchmark data sets.